1. Field of the Invention.
This invention relates in general to computerized relational databases, and in particular, to a method, apparatus and program product for performing queries against a relational database using a join index.
2. Description of Related Art.
Relational databases store information in row and column format. A collection of values which are stored in columns and rows is known as a relation. A relation contains zero or more rows and each row is comprised of one or more columns. The set of possible values for a column is referred to as a domain.
Since there can be many columns, and the domains of most columns have fewer values than the total number of rows in the relation, there is usually a fair amount of redundancy in most relations. This redundancy degrades data integrity and wastes storage space.
To minimize such redundancy, a common practice in relational database is to normalize a table, i.e., to divide a table into a number of smaller tables, each of which contains a subset of the columns of the original table. The smaller tables have at least one commonly-used column, which allows the original table to be recreated by a join operation on the smaller tables, should the need arises.
The original table is referred to as a denormalized relation and the smaller tables are referred to as normalized relations. Less total storage space is used after normalization, because unique information is stored only once in normalized relations. Moreover, normalization enhances data integrity, since there is no need to maintain redundant data.
Normalization also minimizes data redundancy, but can be expensive if join operations are used too often to recreate the original data. Thus, there is a need in the art for techniques that reduce the cost of recreating denormalized relations through join operations without increasing data redundancy.